package advance.day01;

/**
 * 描述：
 *      KMP算法解决字符串匹配问题
 * @author hl
 * @version 1.0
 * @date 2020/11/3 15:02
 */
public class Kmp {
    public static int getIndexOf(String str1,String str2){
        if (str1.length() < str2.length()) {
            return -1;
        }
        int[] next = getNextArr(str2);
        int p1 = 0;
        int p2 = 0;
        while(p1 < str1.length() && p2 < str2.length()){
            if (str1.charAt(p1) == str2.charAt(p2)) {
                p1++;
                p2++;
            }else if (next[p2] == -1) {
                p1++;
            }else{
                p2 = next[p2];
            }
        }
        return p2 == str2.length() ? p1 - p2 : -1;
    }

    /**
     * 求next数组（next数组存放的是索引位置上一个元素的公共前后缀的长度）
     * @param str2
     * @return
     */
    private static int[] getNextArr(String str2) {
        if(str2.length() < 2){
            return new int[str2.length()];
        }
        char[] chs = str2.toCharArray();
        int[] next = new int[str2.length()];//
        next[0] = -1;
        next[1] = 0;
        int cn = 0;//当前位置的最长前缀的下一个位置，从0开始
        int i = 2;
        while(i < next.length){
            if (chs[cn] == chs[i - 1]) {
                next[i++] = ++cn;
            }else if (cn > 0) {
                cn = next[cn];
            }else{
                next[i++] = 0;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";
        System.out.println(getIndexOf(str, match));
    }
}
